﻿#include <iostream>
#include <vector>

using namespace std;

static void swap(char* pStr, int index1, int index2)
{
    if (index1 == index2) return;

    pStr[index1] = pStr[index1] ^ pStr[index2];
    pStr[index2] = pStr[index1] ^ pStr[index2];
    pStr[index1] = pStr[index1] ^ pStr[index2];
}

/**
 * chars[i..]范围上，所有的字符，都可以在i位置上，后续都去尝试
 * chars[0..i-1]范围上，是之前做的选择
 * 举例："abc" ->
 * 'a' + "bc" -> 'a' + 'b' + 'c'
 *               'a' + 'c' + 'b'
 * 'b' + "ac" -> 'b' + 'a' + 'c'
 *               'b' + 'c' + 'a'
 * 'c' + "ba" -> 'c' + 'b' + 'a'
 *               'c' + 'a' + 'b'
 * @param pStr
 * @param index
 * @param charList 请把所有的字符串形成的全排列，加入到list中
 */
static void process(char* pStr, const int size, const int index, vector<char*>& charList)
{
    if (index > size) return;

    if (index == size)
    {
        char* pOut = (char*)malloc(size + 1);
        memset(pOut, 0, size + 1);
        memcpy(pOut, pStr, size);
        charList.push_back(pOut);
    }

    bool appears[26] = { 0 };
    for (int i = index; i < size; i++)
    {
        if (!appears[pStr[i] - 'a'])
        {
            appears[pStr[i] - 'a'] = true;
            swap(pStr, i, index);
            process(pStr, size, index + 1, charList);
            swap(pStr, i, index);
        }
    }
}

// 打印一个字符串的全部排列，要求不出现重复的排列
int main_AllPermutationsOfString()
{
    vector<char*> charList;
    char msg[0xff];
    sprintf_s(msg, "%s", "abbc");
    int len = strlen(msg);
    process(msg, len, 0, charList);

    for (vector<char*>::iterator itor = charList.begin(); itor != charList.end(); ++itor)
    {
        printf("%s\n", *itor);
        free(*itor);
    }

    return 0;
}